class CaminosMinimos {
	// Camino minimo de cada vortice a los restantes. Se utiliza el
	// algoritmo de Dijkstra.
	public static int[][] caminosMinimos(int[][] m) {
		int tamanho = m.length;
		int[][] distancias = new int[tamanho][tamanho];
		boolean[] visitados = new boolean[tamanho];
		int cont = 0, v = 0, i = 0, j = 0, w = 0, minimo = 0;

		for (i = 0; i < tamanho; i++) {
			// visitados = new boolean[m.length];

			for (j = 0; j < visitados.length; j++) {
				visitados[j] = false;
			}

			visitados[i] = true; // Java inicializa os booleanos a false
			for (j = 0; j < tamanho; j++) {
				distancias[i][j] = m[i][j];
			}

			cont = tamanho - 2;
			while (cont-- > 0) {
				v = 0; minimo = Integer.MAX_VALUE;
				for (j = 0; j < tamanho; j++) {
					if (visitados[j])
						continue;
					if (distancias[i][j] < minimo) {
						minimo = distancias[i][j];
						v = j;
					}
				}

				visitados[v] = true;

				for (w = 0; w < tamanho; w++) {
					if (visitados[w])
						continue;
					if (distancias[i][w] > distancias[i][v] + m[v][w])
						distancias[i][w] = distancias[i][v] + m[v][w];
				}
			}
		}

		return distancias;
	}

	public String toString() {
		return "caminos minimos mediante algoritmo de Dijkstra";
	}
}
